package com.monkeyboy.tree;

/**
 * 题目：
 * 二叉树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
 * <p>
 * 解题思路：
 * 1. 确定root节点（后续遍历，说明最后一个节点就是根节点）
 * 2. 根节点左边的节点比根节点小，右边的比根节点大，所以根据这个特性把序列分成两段
 * 3. 判断上一步中分开的两段中是否有比根节点大或者根节点小的，如果左边有比根节点大或者右边有比根节点小的就返回false
 * 4. 左右两边再递归1，2，3步骤
 *
 * @Author Gavin
 * @date 2021.04.20 12:04
 */
public class Tree07 {
    public boolean helpVerify(int[] sequence, int start, int root) {
        if (start >= root) return true;
        int key = sequence[root];
        int i;
        //找到左右子数的分界点
        for (i = start; i < root; i++)
            if (sequence[i] > key)
                break;
        //在右子树中判断是否含有小于root的值，如果有返回false
        for (int j = i; j < root; j++)
            if (sequence[j] < key)
                return false;
        return helpVerify(sequence, start, i - 1) && helpVerify(sequence, i, root - 1);
    }

    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        return helpVerify(sequence, 0, sequence.length - 1);
    }
}
